package com.csdemos.algs.graphs;

import java.util.LinkedList;

public class DFS {
	
	private static final int WHITE = 0;
	private static final int GRAY = 1;
	private static final int BLACK = 2;
	
	
	public static String parenthesis(Graph graph) {
		int[] vertexs = graph.getVertexs();
		int[] color = new int[vertexs.length];
		int[] P = new int[vertexs.length];
		StringBuilder result = new StringBuilder();
		for (int u : vertexs) {
			color[u] = WHITE;
			P[u] = -1;
		}
		for (int u : vertexs) {
			if (color[u] == WHITE) {
				DFS_Visit(graph, u, color, P, result);
			}
		}
		return result.toString();
	}
	
	private static void DFS_Visit(Graph graph, int u, int[] color, int[] P, StringBuilder buffer) {
		color[u] = GRAY;
		buffer.append("(").append(u).append(" ");
		for (int v : graph.getAdjecents(u)) {
			if (color[v] == WHITE) {
				P[v] = u;
				DFS_Visit(graph, v, color, P, buffer);
			}
		}
		color[u] = BLACK;
		buffer.append(u).append(")");
	}
	
	private static int DFS_Visit_F(Graph graph, int u, int[] s, int[] f, int k, int[] time, int[] color, int[] P) {
		color[u] = GRAY;
		time[0]++;
		// d[u] = time
		//buffer.append("(").append(u).append(" ");
		for (int v : graph.getAdjecents(u)) {
			if (color[v] == WHITE) {
				P[v] = u;
				k = DFS_Visit_F(graph, v, s, f, k, time, color, P);
			}
		}
		color[u] = BLACK;
		s[k--] = u;
		f[u] = ++time[0];
		//buffer.append(u).append(")");
		return k;
	}
	
	
	public static String Strongly_Connected_Components(Graph graph) {
		// DFS(G)
		int[] vertexs = graph.getVertexs();
		int[] color = new int[vertexs.length];
		int[] P = new int[vertexs.length];
		int[] f = new int[vertexs.length];
		int[] s = new int[vertexs.length];
		int k = f.length - 1;
		int[] time = new int[] {0};
		for (int u : vertexs) {
			color[u] = WHITE;
			P[u] = -1;
		}
		for (int u : vertexs) {
			if (color[u] == WHITE) {
				k = DFS_Visit_F(graph, u, s, f, k, time, color, P);
			}
		}
		// G^T
		graph = graph.transpose();
		// DFS(G^T)
		StringBuilder result = new StringBuilder();
		for (int u : vertexs) {
			color[u] = WHITE;
			P[u] = -1;
		}
		for (int u : s) {
			if (color[u] == WHITE) {
				DFS_Visit(graph, u, color, P, result);
			}
		}
		//System.out.println(Arrays.toString(f));
		return result.toString();
	}

	public static LinkedList<Integer> Topological_Sort(Graph graph) {
		int[] vertexs = graph.getVertexs();
		int[] color = new int[vertexs.length];
		int[] P = new int[vertexs.length];
		int[] f = new int[vertexs.length];
		int[] s = new int[vertexs.length];
		int k = f.length - 1;
		int[] time = new int[] {0};
		for (int u : vertexs) {
			color[u] = WHITE;
			P[u] = -1;
		}
		for (int u : vertexs) {
			if (color[u] == WHITE) {
				k = DFS_Visit_F(graph, u, s, f, k, time, color, P);
			}
		}
		LinkedList<Integer> result = new LinkedList<Integer>();
		for (int i = 0; i < s.length; i++) {
			result.addFirst(s[i]);
		}
		return result;
	}
}
